#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        vector<bool> dp0(s.length(), false);
        vector<bool> dp1(s.length(), false);
        int maxSize = 0;
        int left = 0, right = 0;
        for (int i = s.length() - 1; i >= 0; --i) {
            dp0[i] = true;
            int size = 0;
            for (int j = i+1; j < s.length(); ++j) {
                if (s[i] == s[j]) {
                    dp0[j] = (j == i + 1) ? true : dp1[j - 1];
                    if (dp0[j]&&(maxSize < (j - i + 1))) {
                        maxSize = j - i + 1;
                        left = i;
                        right = j;
                    }
                }
                else
                    dp0[j] = false;
            }
            swap(dp0, dp1);
        }
        return s.substr(left, right - left + 1);
    }
};
int main() {
    Solution sol;
    sol.longestPalindrome("abacab");
}